package 力扣_二分查找.旋转数组系列;

/**
 * @author zx
 * @create 2022-10-15 18:07
 */
public class 搜索旋转排序数组II_81 {
    /**
     * @return 这个题和33题是相似的,就是有数组元素会有重复值
     * 并且这道题要过全部测试用例,if()条件必须假定左边有序
     *
     * 而(搜索旋转排序数组_33)这道题要过全部测试用例,if()条件必须假定右边有序
     */
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return true;
            }
            // 有重复元素,重复元素跳过
            if (nums[left] == nums[mid]) {
                left++;
                continue;
            }
            // 如果左边有序
            if(nums[mid] > nums[left]){
                // 目标值在左边
                if(nums[mid] > target && target >= nums[left]){
                    right = mid - 1;
                }else{// 目标值在右边
                    left = mid + 1;
                }
            }else{// 如果右边有序
                // 目标值在右边
                if(nums[mid] < target && target <= nums[right]){
                    left = mid + 1;
                }else{// 目标值在左边
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}
